/**
 * 一个矩形，横着可以且m-1刀，竖着可以且n-1刀，各有代价
 * 问切成单位正方形，最小代价是多少
 * 首先有一个贪心，在横竖内部，代价越高的位置越要先切
 * 因为当竖着切了一刀后，横位置再切代价就会比原来多，当然是代价越小越靠后有利
 * 又因为n和m很小，令Dij表示横着切i刀、竖着切j刀的最小代价
 * 则 Dij = min(D[i-1][j] + Hi * (j + 1), D[i][j-1] + Sj * (i + 1))
 * 因为只有两种情况可以转移到ij。
 */
class Solution {
struct _t{
    int v;
    int p;
    bool operator < (const _t & b) const {
        if(v != b.v) return v > b.v;
        return p < b.p;
    }
};    

vector<vector<int>> D;

public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        static const int INF = 0x7F6F7F8F;
        vector<_t> rows, cols;
        rows.push_back({0, 0});
        cols.push_back({0, 0});
        for(int i=0;i<horizontalCut.size();++i){
            rows.push_back({horizontalCut[i], i + 1});
        }     
        for(int i=0;i<verticalCut.size();++i){
            cols.push_back({verticalCut[i], i + 1});
        }

        sort(rows.begin() + 1, rows.end());
        sort(cols.begin() + 1, cols.end());

        D.assign(rows.size(), vector<int>(cols.size(), 0));

        for(int i=0;i<rows.size();++i){
            for(int j=0;j<cols.size();++j){
                if(0 == i and 0 == j) continue;

                D[i][j] = INF;
                if(i > 0){
                    int cost = rows[i].v * (j + 1);
                    D[i][j] = min(D[i][j], D[i - 1][j] + cost); 
                }
                if(j > 0){
                    int cost = cols[j].v * (i + 1);
                    D[i][j] = min(D[i][j], D[i][j - 1] + cost);
                }
            }
        }

        return D[rows.size() - 1][cols.size() - 1];
    }
};